package com.leetcode.algorithm.二叉树;

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class lc102二叉树的层序遍历 {
    private static String line;
    private static String[] parts;
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while((line=in.readLine())!=null){
            parts=line.split(" ");
            n= parts.length;
            String[] levelOrder=new String[n];
            for (int i = 0; i < n; i++) {
                levelOrder[i]=parts[i];
            }
            TreeNode root=createTree(levelOrder);
            List<List<Integer>> ans=levelOrder(root);
            for (List<Integer> list : ans) {
                for (Integer i : list) {
                    System.out.print(i+" ");
                }
                System.out.println();
            }
        }
        out.flush();
        out.close();
    }

    private static TreeNode createTree(String[] levelOrder) {
        if(levelOrder.length==0||levelOrder[0].equals("null")) return null;
        TreeNode[] nodes=new TreeNode[n];
        for (int i = 0; i < n; i++) {
            if (!levelOrder[i].equals("null")){
                nodes[i]=new TreeNode(Integer.parseInt(levelOrder[i]));
            }
        }
        for (int i = 0; i <n; i++) {
            if (nodes[i]!=null){
                int leftIndex=i*2+1;
                int rightIndex=i*2+2;
                if(leftIndex<n) nodes[i].left=nodes[leftIndex];
                if (rightIndex<n) nodes[i].right=nodes[rightIndex];
            }
        }
        return nodes[0];
    }

    private static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        Deque<TreeNode> deque=new ArrayDeque<>();
        if (root!=null){
            deque.add(root);
        }
        while(!deque.isEmpty()){
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int i=deque.size();i>0;i--){
                TreeNode node=deque.poll();
                tmp.add(node.val);
                if (node.left!=null) deque.add(node.left);
                if (node.right!=null) deque.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}
